# 29/100 链表-删除链表的倒数第N个结点
# leetcode第19题: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/20
from typing import Optional
from leetcode.bds import ListNode, ListConvert
from leetcode import test


def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """我的方法，在遍历指针curr后面长度为n的位置增加一个指针n_node"""
    curr = head
    pre_n_node, n_node, k = None, head, 1
    while curr.next:
        if k == n:
            curr, pre_n_node, n_node = curr.next, n_node, n_node.next
        else:
            k += 1
            curr = curr.next
    if pre_n_node:
        pre_n_node.next = n_node.next
    else:
        head = n_node.next
    return ListConvert.link_to_list(head)


def removeNthFromEnd_opt(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """优化的方法，减少了一个指针"""
    dummy = ListNode(0, head)
    fast = head
    slow = dummy
    for i in range(n):
        fast = fast.next

    while fast:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return ListConvert.link_to_list(dummy.next)


if __name__ == '__main__':
    head1 = ListConvert.list_to_link([1, 2, 3, 4, 5])
    head2 = ListConvert.list_to_link([1])
    head3 = ListConvert.list_to_link([1, 2])
    head4 = ListConvert.list_to_link([1, 2])

    inp = [{"head": head1, "n": 2}, {"head": head2, "n": 1}, {"head": head3, "n": 1}, {"head": head4, "n": 2}, ]
    out = [[1, 2, 3, 5], [], [1], [2]]

    test.test_function(removeNthFromEnd, inp, out)
    test.test_function(removeNthFromEnd_opt, inp, out)
